/**
 * 暴力解法(超时)
 */

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for(int i = 0;i < prices.length - 1;i ++){
            for(int j = i + 1;j < prices.length;j ++){
                ans = Math.max(ans,prices[j] - prices[i]);
            }
        }
        return ans;
    }
}

/**
 * 优化后的解法(只需要一次遍历)
 */
class Solution1 {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int temp = prices[0];
        for(int i = 0;i < prices.length;i ++){
            ans = Math.max(ans,prices[i] - temp);//每次股票利润达到新高的时候就重新记录
            temp = Math.min(temp,prices[i]);//每次股票达到新低的时候就重新记录

        }
        return ans;
    }
}